#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>
#include <sys/time.h>

typedef struct {
    int* parent;
    int* size;
    int count;
    int M;      // 生成的总对数
    int edges;  // 有效合并次数
} UnionFind;

// 算法类型枚举
typedef enum {
    QUICK_FIND,
    QUICK_UNION,
    WEIGHTED_UNION,
    PATH_COMPRESSION
} AlgorithmType;

// 时间获取函数（毫秒精度）
long long get_time_ms() {
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return (long long)tv.tv_sec * 1000 + tv.tv_usec / 1000;
}

UnionFind* uf_init(int N, AlgorithmType type) {
    UnionFind* uf = malloc(sizeof(UnionFind));
    uf->parent = malloc(N * sizeof(int));
    uf->size = (type >= WEIGHTED_UNION) ? malloc(N * sizeof(int)) : NULL;
    
    for (int i = 0; i < N; i++) {
        uf->parent[i] = i;
        if (uf->size) uf->size[i] = 1;
    }
    
    uf->count = N;
    uf->M = 0;
    uf->edges = 0;
    return uf;
}

void uf_destroy(UnionFind* uf) {
    free(uf->parent);
    if (uf->size) free(uf->size);
    free(uf);
}

// 带路径压缩的查找
int pc_find(UnionFind* uf, int p) {
    int root = p;
    while (root != uf->parent[root]) {
        root = uf->parent[root];
    }
    // 路径压缩
    while (p != root) {
        int next = uf->parent[p];
        uf->parent[p] = root;
        p = next;
    }
    return root;
}

// 标准查找
int std_find(UnionFind* uf, int p) {
    while (p != uf->parent[p]) {
        p = uf->parent[p];
    }
    return p;
}

void run_test(int N, AlgorithmType type) {
    UnionFind* uf = uf_init(N, type);
    long long start_time = get_time_ms();
    
    while (uf->count > 1) {
        uf->M++;  // 总尝试次数计数
        
        int p = rand() % N;
        int q = rand() % N;
        
        int rootP, rootQ;
        
        // 选择查找算法
        if (type == PATH_COMPRESSION) {
            rootP = pc_find(uf, p);
            rootQ = pc_find(uf, q);
        } else {
            rootP = std_find(uf, p);
            rootQ = std_find(uf, q);
        }
        
        if (rootP != rootQ) {
            // 选择合并策略
            if (type == QUICK_FIND) {
                int new_root = uf->parent[rootQ];
                for (int i = 0; i < N; i++) {
                    if (uf->parent[i] == rootP) {
                        uf->parent[i] = new_root;
                    }
                }
            } 
            else if (type >= WEIGHTED_UNION) {
                if (uf->size[rootP] < uf->size[rootQ]) {
                    uf->parent[rootP] = rootQ;
                    uf->size[rootQ] += uf->size[rootP];
                } else {
                    uf->parent[rootQ] = rootP;
                    uf->size[rootP] += uf->size[rootQ];
                }
            } 
            else { // Quick-Union
                uf->parent[rootP] = rootQ;
            }
            
            uf->count--;
            uf->edges++;
        }
    }
    
    long long elapsed = get_time_ms() - start_time;
    
    // 输出结果
    const char* alg_name[] = {"QuickFind", "QuickUnion", "Weighted", "PathCompress"};
    printf("| %-7d | %-12s | %-9d | %-7d | %-5lldms |\n", 
           N, alg_name[type], uf->M, uf->edges, elapsed);
    
    // 验证最终连通性
    int root = pc_find(uf, 0);
    for (int i = 1; i < N; i++) {
        assert(pc_find(uf, i) == root);
    }
    
    uf_destroy(uf);
}

/**
 * File:BenchmarkForUF3.c
 * ----------------------
 * 大模型提示词：
 * ![表1.1](../../images/table11.png)
 * 我是正在学习算法，但我是一个算法小白，对算法的实证研究一窍不通。
 * 你是一位专家，帮我设计一份有关连通性问题求解算法的实证研究，并使用C语言实现。
 * ---------------------- 
 * 
 */
int main() {
    srand(time(NULL));
    
    int test_cases[] = {1000, 2500, 5000, 10000, 25000, 50000, 100000};
    int num_tests = sizeof(test_cases)/sizeof(int);
    
    // 打印表头
    printf("| %-7s | %-12s | %-9s | %-7s | %-8s |\n", 
           "N", "Algorithm", "M", "Edges", "Time");
    printf("|---------|--------------|-----------|---------|----------|\n");
    
    for (int i = 0; i < num_tests; i++) {
        int N = test_cases[i];
        
        // 测试所有算法
        for (int alg = 0; alg <= PATH_COMPRESSION; alg++) {
            run_test(N, (AlgorithmType)alg);
        }
        
        printf("\n"); // 不同N值之间空行分隔
    }
    
    return 0;
}